package com.lie.prepare.algorithm.sort;

import java.util.Arrays;

import static com.lie.prepare.util.Print.*;
/**
 * Created by lie on 2018/4/12.
 * 快速排序
 *  时间复杂度是 n*log(n)
 *  最差复杂度是 O(n^2)，给定的序列已经是完全排序好的时候，会触发这个，得到一个斜二叉树
 *
 *  它是不稳定排序
 */
public class QuickSort {

    //分区
    private static int part(int[] array, int low, int high){
        //设置基准value
        int p = array[high];//也可以定为array[low]
        //最终要找到的中位下标
        //它的意义在于，它的左边，所有值都小于基准p，它的右边，所有值都大于基准p
        //尽管左区或者右区里面并不是从小到大排序的，但这会在之后的递归中实现
        //注意中位下标并不是简单的数组长度的一半
        int mid = low;
        int temp;

        for (int i = low; i < high; i++) {
            if (array[i] < p) {
                //这里触发以后，由于mid的增长是会被高过基准value的"巨人"
                if (array[i] != array[mid]){
                    temp = array[i];
                    array[i] = array[mid];
                    array[mid] = temp;
                }
                //只有小于基准的，就会触发中位下标移动
                //而高于基准的，是不会进入这个循环里的
                //可以想象，一次遍历过后
                //mid自然会停留在所有小于基准value的数字之后
                mid++;
            }
        }

        //把基准放到中位那边去
        temp = array[high];
        array[high] = array[mid];
        array[mid] = temp;
        print("mid = "+ mid);
        return mid;
    }

    public static void doSort(int[] array, int low, int high){
        if (low < high) {
            int mid = part(array, low, high);
            doSort(array, low, mid-1);
            doSort(array, mid+1, high);
        }
    }

    public static void main(String[] args){
//        int[] sort = { 1, 2, 3, 5};
        int[] sort = { 1, 2, 4, 3};
//        int[] sort = { 54, 31, 12, 89, 33, 66, 12, 68, 20 };
        print("排序前= " + Arrays.toString(sort));

        doSort(sort, 0, sort.length-1);
        print("排序后= " + Arrays.toString(sort));
    }
}
